Definition

AC⁰ is a subclass of ACⁱ, corresponding to constant-depth (O(1)O(1)), unbounded-fanin of AND and OR gates (NOT gates allowed at inputs), polynomial-size circuits

in other words,

Let Q⊆Σ∗Q \subseteq \Sigma^*, then say Q∈𝐀𝐂0Q \in \mathbf{AC}^0 if there exists a family of boolean circuits (𝖢n)n∈ℕ(\mathsf{C}_n)_{n \in \mathbb{N}} such that

  1. depth of every 𝖢n\mathsf{C}_n is bounded by a fixed constant
  2. |𝖢n|=nO(1)|\mathsf{C}_n| = n^{O(1)}
  3. let x∈Σ∗x \in \Sigma^*, then (x∈Qx \in Q if and only if 𝖢|x|(x)=1\mathsf{C}_{|x|}(x)=1); in particular 𝖢n\mathsf{C}_n has nn input gates
  4. (𝖢n)n∈ℕ(\mathsf{C}_n)_{n \in \mathbb{N}} is dlogtime-uniform, i.e. there is a deterministic logtime Turing machine 𝕄\mathbb{M} which on input 1n1^n outputs circuit 𝖢n\mathsf{C}_n; more precisely 𝕄\mathbb{M} recognizes language {(b,i,1n)|the ith bit of the binary encoding of 𝖢n is b}\{ (b,i,1^n) | \text{the }i\text{th bit of the binary encoding of }\mathsf{C}_n\text{ is }b\}

(fanin meaning number of inputs to a logic gate)

Hierarchy of languages (based on number of layers)

can divide 𝐀𝐂0\mathbf{AC}^0 further into hierarchy of languages based on number of layers

𝐀𝐂10⊂𝐀𝐂20⊂...⊂𝐀𝐂0=⋃d=1∞𝐀𝐂d0\mathbf{AC}^0_1 \subset \mathbf{AC}^0_2 \subset ... \subset \mathbf{AC}^0 = \bigcup_{d=1}^\infty \mathbf{AC}^0_d

See also

References

  1. https://complexityzoo.net/Complexity_Zoo:A
  2. Y. Chen and J. Flum, “Some lower bounds in parameterized AC0,” Information and Computation, vol. 267, pp. 116–134, Aug. 2019, doi: 10.1016/j.ic.2019.03.008.
  3. https://en.wikipedia.org/wiki/AC0